﻿//
// KwData v2.0.0
// Copyright © 2009-2012 - Kasey Osborn (Kasewick@gmail.com)
// Ms-PL - Use and redistribute freely
//
// File:    BtreeDictionaryOps.cs
// Purpose: Define high level internal tree operations.
//

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace Kw.Data
{
    public partial class BtreeDictionary<TKey, TValue>
    {
        #region Internal methods

        /// <summary>Get the leftmost leaf.</summary>
        /// <remarks>Used by iteration.</remarks>
        internal Leaf<TKey, TValue> FirstLeaf
        {
            get
            {
                for (Node<TKey> node = root; ; node = ((Branch<TKey>) node).FirstChild)
                {
                    Leaf<TKey, TValue> leaf = node as Leaf<TKey, TValue>;
                    if (leaf != null)
                        return leaf;
                }
            }
        }


        /// <summary>Perform lite search for key.</summary>
        /// <param name="key">Target of search.</param>
        /// <param name="index">When found, holds index of returned Leaf.</param>
        /// <returns>Leaf holding target if found; otherwise <b>null</b> if not found.</returns>
        internal Leaf<TKey, TValue> Find (TKey key, out int index)
        {
            //  Method is unfolded on comparer to improve speed 5%.
            if (comparer == Comparer<TKey>.Default)
                for (Node<TKey> node = root; ; )
                {
                    int nodeIndex = node.Search (key);

                    Branch<TKey> branch = node as Branch<TKey>;
                    if (branch == null)
                    {
                        index = nodeIndex;
                        return nodeIndex < 0 ? null : (Leaf<TKey, TValue>) node;
                    }

                    node = branch.GetChild (nodeIndex < 0 ? ~nodeIndex : nodeIndex + 1);
                }
            else
            {
                for (Node<TKey> node = root; ; )
                {
                    int nodeIndex = node.Search (key, comparer);

                    Branch<TKey> branch = node as Branch<TKey>;
                    if (branch == null)
                    {
                        index = nodeIndex;
                        return nodeIndex < 0 ? null : (Leaf<TKey, TValue>) node;
                    }

                    node = branch.GetChild (nodeIndex < 0 ? ~nodeIndex : nodeIndex + 1);
                }
            }
        }


        private void Insert (TreePath<TKey, TValue> path, TKey key, TValue value)
        {
            Leaf<TKey, TValue> leaf = (Leaf<TKey, TValue>) path.TopNode;
            int leafIndex = path.TopNodeIndex;

            if (leaf.NotFull)
            {
                leaf.Insert (leafIndex, key, value);
                ++Count;
                return;
            }

            // Right split a new leaf.
            Leaf<TKey, TValue> newLeaf = new Leaf<TKey, TValue> (leaf);

            if (newLeaf.RightLeaf == null && leafIndex == leaf.KeyCount)
                // Densify sequential loads.
                newLeaf.Add (key, value);
            else
            {
                int halfway = leaf.KeyCount / 2 + 1;

                if (leafIndex < halfway)
                {   // Left-side insert: Copy right side to the split leaf.
                    newLeaf.Add (leaf, halfway - 1, leaf.KeyCount);
                    leaf.Truncate (halfway - 1);
                    leaf.Insert (leafIndex, key, value);
                }
                else
                {   // Right-side insert: Copy split leaf parts and new key.
                    newLeaf.Add (leaf, halfway, leafIndex);
                    newLeaf.Add (key, value);
                    newLeaf.Add (leaf, leafIndex, leaf.KeyCount);
                    leaf.Truncate (halfway);
                }
            }

            // Promote anchor of split leaf.
            ++Count;
            PromoteKey (path, newLeaf.GetKey (0), (Node<TKey>) newLeaf);
        }


        private void PromoteKey (TreePath<TKey, TValue> path, TKey key, Node<TKey> newNode)
        {
            for (; ; )
            {
                if (path.Height == 1)
                {
                    // Graft new root.
                    Debug.Assert (root == path.TopNode);
                    root = new Branch<TKey> (path.TopNode, Order);
                    root.Add (key, newNode);
                    ++height;
                    break;
                }

                path.Pop ();
                Branch<TKey> branch = (Branch<TKey>) path.TopNode;
                int branchIndex = path.TopNodeIndex;

                if (branch.NotFull)
                {
                    branch.InsertKey (branchIndex, key);
                    branch.Insert (branchIndex + 1, newNode);
                    break;
                }

                // Right split an overflowing branch.
                Branch<TKey> newBranch = new Branch<TKey> (branch);
                int halfway = (branch.KeyCount + 1) / 2;

                if (branchIndex < halfway)
                {
                    // Split with left-side insert.
                    for (int i = halfway; ; ++i)
                    {
                        if (i >= branch.KeyCount)
                        {
                            newBranch.Add (branch.GetChild (i));
                            break;
                        }
                        newBranch.Add (branch.GetKey (i), branch.GetChild (i));
                    }

                    TKey newPromotion = branch.GetKey (halfway - 1);
                    branch.Truncate (halfway - 1);
                    branch.InsertKey (branchIndex, key);
                    branch.Insert (branchIndex + 1, newNode);
                    key = newPromotion;
                }
                else
                {
                    // Split branch with right-side insert (or cascade promote).
                    int moveIndex = halfway;

                    if (branchIndex > halfway)
                    {
                        for (; ; )
                        {
                            ++moveIndex;
                            newBranch.Add (branch.GetChild (moveIndex));
                            if (moveIndex >= branchIndex)
                                break;
                            newBranch.AddKey (branch.GetKey (moveIndex));
                        }
                        newBranch.AddKey (key);
                        key = branch.GetKey (halfway);
                    }

                    newBranch.Add (newNode);

                    while (moveIndex < branch.KeyCount)
                    {
                        newBranch.AddKey (branch.GetKey (moveIndex));
                        ++moveIndex;
                        newBranch.Add (branch.GetChild (moveIndex));
                    }

                    branch.Truncate (halfway);
                }

                newNode = newBranch;
            }
        }


        private void Delete (TreePath<TKey, TValue> path)
        {
            int leafIndex = path.TopNodeIndex;
            Leaf<TKey, TValue> leaf = (Leaf<TKey, TValue>) path.TopNode;

            leaf.Remove (leafIndex);
            --Count;

            if (leafIndex == 0)
                if (leaf.KeyCount != 0)
                    path.Pivot = path.TopNode.GetKey (0);
                else
                {
                    // Empty leaf.  Prune unless tree is empty.
                    Leaf<TKey, TValue> leftLeaf = (Leaf<TKey, TValue>) path.LeftNode;
                    if (leftLeaf != null)
                        leftLeaf.RightLeaf = leaf.RightLeaf;
                    else
                    {
                        if (leaf.RightLeaf == null)
                            // No siblings.  Let one leaf survive.
                            return;

                        Debug.Assert (true, "only on leftmost if order=2");
                    }

                    Prune (path);
                    return;
                }

            if (leaf.KeyCount < leaf.KeyCapacity / 2)
            {
                Leaf<TKey, TValue> right = leaf.RightLeaf;
                if (right != null)
                    if (leaf.KeyCount + right.KeyCount > leaf.KeyCapacity)
                    {
                        // Balance leafs by shifting sibling's pairs from right leaf.
                        int shifts = leaf.KeyCapacity - (leaf.KeyCount + right.KeyCount - 1) / 2;
                        leaf.Add (right, 0, shifts);
                        right.Remove (0, shifts);
                        path.TraverseRight ();
                        path.Pivot = path.TopNode.GetKey (0);
                    }
                    else
                    {
                        // Join leaf by coalescing the right sibling's pairs.
                        leaf.Add (right, 0, right.KeyCount);
                        leaf.RightLeaf = right.RightLeaf;
                        path.TraverseRight ();
                        Prune (path);
                    }
            }
        }


        // Leaf has been emptied, now non-lazy delete its pivot.
        private void Prune (TreePath<TKey, TValue> path)
        {
            for (; ; )
            {
                Debug.Assert (path.Height > 0);
                path.Pop ();

                Branch<TKey> branch = (Branch<TKey>) path.TopNode;
                if (path.TopNodeIndex == 0)
                {
                    if (branch.KeyCount == 0)
                        // Cascade when rightmost branch is empty.
                        continue;

                    // Rotate pivot for first child.
                    TKey pivot0 = branch.GetKey (0);
                    branch.RemoveKey (0);
                    branch.RemoveChild (0);
                    path.Pivot = pivot0;
                }
                else
                {
                    // Typical branch pivot delete.
                    branch.RemoveKey (path.TopNodeIndex - 1);
                    branch.RemoveChild (path.TopNodeIndex);
                }

                Branch<TKey> right = (Branch<TKey>) path.TraverseRight ();
                if (right == null)
                {
                    if (branch == root && branch.KeyCount == 0)
                    {
                        // Prune the empty root.
                        Branch<TKey> newRoot = branch.FirstChild as Branch<TKey>;
                        if (newRoot != null)
                        {
                            root = (Branch<TKey>) branch.FirstChild;
                            --height;
                        }
                    }
                    return;
                }

                if (branch.KeyCount + right.KeyCount < branch.KeyCapacity)
                {
                    // Coalesce left: move pivot and right sibling nodes.
                    branch.AddKey (path.Pivot);

                    for (int i = 0; ; ++i)
                    {
                        branch.Add (right.GetChild (i));
                        if (i >= right.KeyCount)
                            break;
                        branch.AddKey (right.GetKey (i));
                    }

                    // Cascade.
                    continue;
                }

                if (branch.KeyCount < branch.KeyCapacity / 2)
                {
                    int shifts = (right.KeyCount - branch.KeyCount) / 2 - 1;

                    // Balance branches to keep ratio.  Rotate thru the pivot.
                    branch.AddKey (path.Pivot);

                    // Shift pairs from right sibling.
                    for (int rightIndex = 0; ; ++rightIndex)
                    {
                        branch.Add (right.GetChild (rightIndex));

                        if (rightIndex >= shifts)
                            break;

                        branch.AddKey (right.GetKey (rightIndex));
                    }

                    path.Pivot = right.GetKey (shifts);
                    right.Remove (0, shifts + 1);
                }

                return;
            }
        }

        #endregion
    }
}
